#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mpi.h"

#define PRINTDEBUG

#define MAXLEN 100
#define MAXSLEN 15000

#define MIN(a,b)	((a) < (b) ? (a) : (b))
#define MAX(a,b)	((a) > (b) ? (a) : (b))

char	sname[MAXLEN], tname[MAXLEN];
char	sstring[MAXSLEN], tstring[MAXSLEN];
int	lcs[MAXSLEN][MAXSLEN];
FILE	*sfp, *tfp;

int main(int argc, char *argv[]) {
	int	i, j;
	int	slen, tlen;
	double	t1, t2;
	int size,rank;
	MPI_Status status;

	MPI_Init(&argc,&argv);
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);
	MPI_Comm_size(MPI_COMM_WORLD,&size);

	switch(argc) {
		case 3:
			strcpy(sname, *++argv);
			if ((sfp = fopen(sname, "r")) == NULL) {
				fprintf(stderr, "lcs1:  can't open %s\n", sname);
				exit(1);
			}
			printf("sname:%s\n",sname);
			strcpy(tname, *++argv);
			if ((tfp = fopen(tname, "r")) == NULL) {
				fprintf(stderr, "lcs1:  can't open %s\n", tname);
				exit(1);
			}
			printf("tname:%s\n",tname);

			break;
		default:
			fprintf(stderr, "usage: lcs1 sfile tfile\n");
			exit(1);
			break;
	}

	slen = fread(sstring, 1, MAXSLEN, sfp);
	fclose(sfp);
	printf("slen:%d\t",slen);
	sstring[--slen] = '\0';
	printf("sstring:%s\n",sstring);

	while(!feof(tfp))
	{
	tlen = fread(tstring, 1, MAXSLEN, tfp);
	fgets(tstring, MAXSLEN, tfp);
	tstring[--tlen] = '\0';

	printf("tlen:%d\t",tlen);
	printf("tstring:%s",tstring);
	}
	fclose(tfp);
/*
	if (rank == 0)
	{
		for (i = 0 ; i < slen ; i ++)
		{
			int temp = (slen-1)%size;
			MPI_Send(sstring, 1, MPI_INT, temp, 1,  MPI_COMM_WORLD);
		}
		MPI_Recv(sstring, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
	}
	else
	{
		MPI_Recv(sstring, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
	}
*/

	lcs[0][0] = 0;
	for (j = 1; j <= tlen; j++) {
		lcs[0][j] = lcs[0][j-1];
	}

	for (i = 1; i <= slen; i++) {
		lcs[i][0] = lcs[i-1][0];

		for (j = 1; j <= tlen; j++) {
			lcs[i][j] = MAX(lcs[i-1][j], lcs[i][j-1]);

			if (sstring[i-1] == tstring[j-1]) {
				lcs[i][j] = MAX(lcs[i][j], lcs[i-1][j-1] + 1);
			} else {
				lcs[i][j] = MAX(lcs[i][j], lcs[i-1][j-1]);
			}
		}
	}

	printf("Final LCS = %d, percent similarity = %1.3f\n", lcs[slen][tlen], (double)lcs[slen][tlen] / MIN(slen, tlen));

#ifdef PRINTDEBUG
	printf("\nLCS matrix:\n");
	printf("      ");
	for (j = 1; j <= tlen; j++)
		printf(" %c ", tstring[j-1]);
	printf("\n");
	printf("   ");
	for (j = 0; j <= tlen; j++)
		printf("%3d", lcs[0][j]);
	printf("\n");
	for (i = 1; i <= slen; i++) {
		printf(" %c ", sstring[i-1]);
		for (j = 0; j <= tlen; j++)
			printf("%3d", lcs[i][j]);
		printf("\n");
	}
	printf("\n");
#endif

	MPI_Finalize();
	return 0;
}
